﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class NewDCube
    {
        private Dictionary<int, int> answer = new Dictionary<int, int>();
        public NewDCube()
        {
            int T = GetConsole.GetInt();
            int[] nowSize = new int[3] { 1, 1, 1 };
            answer.Add(GetKey(nowSize), 1);
            while (T-- > 0)
            {

                nowSize[0] = nowSize.Min();
                nowSize[1] = nowSize[0];
                nowSize[2] = nowSize[0];
                int[] endSize = new int[3];
                endSize[0] = GetConsole.GetInt();
                endSize[1] = GetConsole.GetInt();
                endSize[2] = GetConsole.GetInt();
                SortSize(endSize);
                int value = 0;
                if (answer.ContainsKey(GetKey(endSize)))
                {
                    value = answer[GetKey(endSize)];
                }
                else
                {
                    while (Next(nowSize, endSize))
                    {
                        //Console.WriteLine(GetKey(nowSize));
                        value = FindValue(nowSize);
                    }
                }
                Console.WriteLine(value);
            }
        }
        public int FindValue(int[] size)
        {
            if (answer.ContainsKey(GetKey(size)))
            {
                return answer[GetKey(size)];
            }
            int minValue = int.MaxValue;
            if (size[0] == size[1] && size[1] == size[2])
            {
                answer.Add(GetKey(size), 1);
                return 1; 
            }
            for (int i = 1; i < size[0]/2 + 1; i++)
            {
                int[] newSize1 = new int[] { i, size[1], size[2] };
                SortSize(newSize1);
                int[] newSize2 = new int[] { size[0] - i, size[1], size[2] };
                SortSize(newSize2);
                int value = answer[GetKey(newSize1)] + answer[GetKey(newSize2)];
                if (value < minValue)
                { minValue = value; }
            }
            for (int i = 1; i < size[1] / 2 + 1; i++)
            {
                int[] newSize1 = new int[] { size[0], i, size[2] };
                SortSize(newSize1);
                int[] newSize2 = new int[] { size[0], size[1] - i, size[2] };
                SortSize(newSize2);
                int value = answer[GetKey(newSize1)] + answer[GetKey(newSize2)];
                if (value < minValue)
                { minValue = value; }
            }
            for (int i = 1; i < size[2] / 2 + 1; i++)
            {
                int[] newSize1 = new int[] { size[0], size[1], i };
                SortSize(newSize1);
                int[] newSize2 = new int[] { size[0], size[1], size[2] - i };
                SortSize(newSize2);
                int value = answer[GetKey(newSize1)] + answer[GetKey(newSize2)];
                if (value < minValue)
                { minValue = value; }
            }
            answer.Add(GetKey(size), minValue);
            return minValue;
        }
        public bool Next(int[] nowSize, int[] endSize)
        {
            nowSize[0]++;
            if (nowSize[0] > endSize[0])
            {
                nowSize[0] = 1;
                nowSize[1]++;
                if (nowSize[1] > endSize[1])
                {
                    nowSize[1] = 1;
                    nowSize[2]++;
                    if (nowSize[2] > endSize[2])
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        public int GetKey(int[] size)
        {
            //return (size[0] * 256 * 256) + (size[1] * 256) + size[2];
            return (size[0] * 1000000) + (size[1] * 1000) + size[2];
        }

        public void SortSize(int[] size)
        {
            int buf = 0;
            if (size[0] < size[1])
            {
                buf = size[0];
                size[0] = size[1];
                size[1] = buf;
            }
            if (size[1] < size[2])
            {
                buf = size[1];
                size[1] = size[2];
                size[2] = buf;
            }
            if (size[0] < size[1])
            {
                buf = size[0];
                size[0] = size[1];
                size[1] = buf;
            }

        }
        public void SetNowSize(int[] nowSize, int[] endSize)
        {
            if (endSize[0] < nowSize[0])
            { nowSize[0] = endSize[0]; }
            if (endSize[1] < nowSize[1])
            { nowSize[1] = endSize[1]; }
            if (endSize[2] < nowSize[2])
            { nowSize[2] = endSize[2]; }
        }
    }
}
